package com.shm.leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 653. 两数之和 IV - 输入 BST
 * 给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
 * <p>
 * 案例 1:
 * <p>
 * 输入:
 * 5
 * / \
 * 3   6
 * / \   \
 * 2   4   7
 * <p>
 * Target = 9
 * <p>
 * 输出: True
 * <p>
 * <p>
 * 案例 2:
 * <p>
 * 输入:
 * 5
 * / \
 * 3   6
 * / \   \
 * 2   4   7
 * <p>
 * Target = 28
 * <p>
 * 输出: False
 *
 * @author SHM
 */
public class TwoSumIV {
    public boolean findTarget(TreeNode root, int k) {
        if (root == null) {
            return false;
        }
        Set<Integer> list = new HashSet<>();
        inOrder(root, list);
        for (Integer integer : list) {
            int key = k - integer;
            if (key != integer && list.contains(key)) {
                return true;
            }
        }
        return false;
    }

    public void inOrder(TreeNode node, Set<Integer> list) {
        if (node == null) {
            return;
        }
        inOrder(node.left, list);
        list.add(node.val);
        inOrder(node.right, list);
    }


    /**
     * 方法三：使用 BST【通过】
     * 算法
     * <p>
     * 在本方法中利用 BST 的性质，BST 的中序遍历结果是按升序排列的。因此，中序遍历给定的 BST，并将遍历结果存储到 listlist 中。
     * <p>
     * 遍历完成后，使用两个指针 ll 和 rr 作为 listlist 的头部索引和尾部索引。然后执行以下操作：
     * <p>
     * 检查 ll 和 rr 索引处两元素之和是否等于 kk。如果是，立即返回 True。
     * <p>
     * 如果当前两元素之和小于 kk，则更新 ll 指向下一个元素。这是因为当我们需要增大两数之和时，应该增大较小数。
     * <p>
     * 如果当前两元素之和大于 kk，则更新 rr 指向上一个元素。这是因为当我们需要减小两数之和时，应该减小较大数。
     * <p>
     * 重复步骤一至三，直到左指针 ll 大于右指针 rr。
     * <p>
     * 如果左指针 ll 到右指针 rr 的右边，则返回 False。
     * <p>
     * 注意，在任何情况下，都不应该增大较大的数，也不应该减小较小的数。这是因为如果当前两数之和大于 kk，不应该首先增大 list[r]list[r] 的值。类似的，也不应该首先减小 list[l]list[l] 的值。
     * <p>
     * 复杂度分析
     * <p>
     * 时间复杂度：O(n)O(n)，其中 nn 是树中节点的数量。本方法需要中序遍历整棵树。
     * <p>
     * 空间复杂度：O(n)O(n)，listlist 中存储 nn 个元素。
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/solution/liang-shu-zhi-he-iv-by-leetcode/
     *
     * @param root
     * @param k
     * @return
     */
    public boolean findTarget_2(TreeNode root, int k) {
        if (root == null) {
            return false;
        }
        List<Integer> list = new ArrayList<>();
        inOrder(root, list);
        int left = 0;
        int right = list.size() - 1;
        while (left < right) {
            if (list.get(left) + list.get(right) > k) {
                right--;
            } else if (list.get(left) + list.get(right) < k) {
                left++;
            } else {
                return true;
            }
        }
        return false;
    }

    public void inOrder(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }
        inOrder(node.left, list);
        list.add(node.val);
        inOrder(node.right, list);
    }

    /**
     * 方法一：使用 HashSet【通过】
     * 最简单的方法就是遍历整棵树，找出所有可能的组合，判断是否存在和为 kk 的一对节点。现在在此基础上做一些改进。
     * <p>
     * 如果存在两个元素之和为 kk，即 x+y=kx+y=k，并且已知 xx 是树上一个节点的值，则只需判断树上是否存在一个值为 yy 的节点，使得 y=k-xy=k−x。基于这种思想，在树的每个节点上遍历它的两棵子树（左子树和右子树），寻找另外一个匹配的数。在遍历过程中，将每个节点的值都放到一个 setset 中。
     * <p>
     * 对于每个值为 pp 的节点，在 setset 中检查是否存在 k-pk−p。如果存在，那么可以在该树上找到两个节点的和为 kk；否则，将 pp 放入到 setset 中。
     * <p>
     * 如果遍历完整棵树都没有找到一对节点和为 kk，那么该树上不存在两个和为 kk 的节点。
     * <p>
     * 复杂度分析
     * <p>
     * 时间复杂度：O(n)O(n)，其中 NN 是节点的数量。最坏的情况下，整棵树被遍历一次。
     * <p>
     * 空间复杂度：O(n)O(n)。最坏的情况下，setset 存储 nn 个节点的值。
     * <p>
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/solution/liang-shu-zhi-he-iv-by-leetcode/
     *
     * @param root
     * @param k
     * @return
     */
    public boolean findTarget_3(TreeNode root, int k) {
        Set<Integer> set = new HashSet<>();
        return find(root, k, set);
    }

    public boolean find(TreeNode node, int k, Set<Integer> set) {
        if (node == null) {
            return false;
        }
        if (set.contains(k - node.val)) {
            return true;
        }
        set.add(node.val);
        return find(node.left, k, set) || find(node.right, k, set);
    }
}
